package me.eg.fifth;

/**
 * 1011. 在 D 天内送达包裹的能力
 * 传送带上的包裹必须在 D 天内从一个港口运送到另一个港口。
 * <p>
 * 传送带上的第 i 个包裹的重量为 weights[i]。每一天，我们都会按给出重量的顺序往传送带上装载包裹。我们装载的重量不会超过船的最大运载重量。
 * <p>
 * 返回能在 D 天内将传送带上的所有包裹送达的船的最低运载能力。
 * <p>
 * 链接：https://leetcode-cn.com/problems/capacity-to-ship-packages-within-d-days
 */
public class ShipWithinDays {
    /**
     * 解法一：二分答案
     * 时间复杂度：O(NlogN)
     * 空间复杂度：O(1)
     *
     * 同样将求解问题转换为判定问题
     * 值域：[Max(nums), Sum(nums)]
     * 解空间有单调性：小于答案，方案都不可行(等价于false)；大于等于答案，方案可行(等价于true)
     * 因此可以用二分查找在值域中寻找答案
     *
     * @param weights
     * @param days
     * @return
     */
    public int shipWithinDays(int[] weights, int days) {
        int left = 0, right = 0;
        for (int weight : weights) {
            left = Integer.max(left, weight);
            right += weight;
        }
        while (left < right) {
            int mid = (left + right) >> 1;
            if (canShip(weights, days, mid)) right = mid;
            else left = mid + 1;
        }
        return right;
    }

    private boolean canShip(int[] weights, int days, int capacity) {
        int consumeDay = 1;
        int weightInPackage = 0;
        for (int weight : weights) {
            weightInPackage += weight;
            if (weightInPackage > capacity) {
                consumeDay++;
                weightInPackage = weight;
            }
        }
        return consumeDay <= days;
    }
}